import java.util.Arrays;

public class Test {
    /**
     * 有效的三角形个数
     *      1.先固定最大的一个数
     *      2.通过双指针来指定left right进行判断
     *      3.根据判断结果进行调整/确定符合条件三角形个数
     */
    public static int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        // 初始化下标
        int count = 0;
        int max = nums.length - 1;
        // 进行判断
        while(max >= 2) {
            int left = 0;
            int right = max - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[max]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
            max--;
        }
        return count;
    }
    public static void main(String[] args) {
        int[] nums = {2,2,3,4};
        System.out.println(triangleNumber(nums));
    }
    /**
     盛最多水的容器
     */
    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while(left < right) {
            int h = Math.min(height[left],height[right]);
            int w = right - left;
            int v = h * w;
            if(max < v) {
                max = v;
            }
            if(height[left] < height[right]) {
                left++;
            }else {
                right--;
            }
        }
        return max;
    }
    public static void main4(String[] args) {
        int[] array = {1,8,6,2,5,4,8,3,7};
        System.out.println(maxArea(array));
        System.out.println();
    }
    /**
     快乐数
     1.创建快慢指针
     2.移动,找到相交点
     3.判断是否为1,为1返回true,不为1返回fasle
     */
    public static boolean isHappy(int n) {
        int slow = n;
        int fast = bitSum(n);
        while(slow != fast) {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return fast == 1;
    }
    /**
     求平方和
     */
    private static int bitSum(int n) {
        int sum = 0;
        while(n != 0) {
            int tmp = n % 10;
            sum += tmp * tmp;
            n = n / 10;
        }
        return sum;
    }
    public static void main3(String[] args) {
        System.out.println(isHappy(2));
    }
    /**
     复写零
     */
    public static void duplicateZeros(int[] arr) {
        int dest = -1;
        int cur = 0;
        while(dest < arr.length) {
            if(arr[cur] != 0) {
                dest++;
            }else {
                dest += 2;
            }
            if(dest < arr.length - 1) {
                cur++;
            }
        }


        while(cur < dest) {
            if(dest >= arr.length) {
                arr[dest - 1] = 0;
                dest -= 2;
                cur--;
            }

            if(arr[cur] != 0) {
                arr[dest] = arr[cur];
                dest--;
            }else {
                int tmp = 2;
                while(tmp != 0) {
                    arr[dest] = arr[cur];
                    dest--;
                    tmp--;
                }
            }
            cur--;
        }
    }
    public static void main2(String[] args) {
        int[] array = {1,0,2,3,0,4,5,0};
        duplicateZeros(array);
        System.out.println();
    }
    /**
     * 移动零
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        int dest = -1;
        for(int cur = 0;cur < nums.length;cur++) {
            if(nums[cur] != 0) {
                swap(nums,cur,++dest);
            }
        }
    }
    private static void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public static void main1(String[] args) {
        int[] array = {0,1,0,3,12};
        moveZeroes(array);
        System.out.println();
    }
}
